#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include "hash.h"
#include "lista.h"


struct hash_iter{
	size_t pos;
	lista_iter_t* iter_l;
	size_t tam_hash;
	claves_t* tabla;	
};

struct _claves {
	lista_t* lista_claves;
};

struct _datos {	
	char* clave;
	void* dato;
};

struct hash {
	claves_t* tabla;
	claves_t* tabla_redimension;
	bool estoy_en_redimension;
	size_t cantidad;
	size_t tamanio;
	hash_destruir_dato_t destruir_dato;
};

hash_iter_t *hash_iter_crear(const hash_t *hash) {
	
	hash_iter_t* iter = malloc(sizeof(hash_iter_t));
	if(!iter) return NULL;

	iter->tam_hash=hash->tamanio;
	
	iter->iter_l=NULL;
	iter->pos=0;
	iter->tabla=NULL;
	
	size_t indice=0;
	
	while(indice<hash->tamanio) {
		if(hash->tabla[indice].lista_claves) {
			
			lista_iter_t* iter_lista=lista_iter_crear(hash->tabla[indice].lista_claves);
			iter->tabla=hash->tabla;
			iter->iter_l=iter_lista;
			iter->pos=indice;
			return iter;	
		}
		indice++;
	}
	
	
	return iter;
	
}
	
hash_t *hash_crear(hash_destruir_dato_t destruir_dato) {
	
	size_t tam= 601;
	int i=0;
	
	hash_t* hash = malloc(sizeof(hash_t));
	if(!hash) return NULL;
    
    hash->tabla = malloc(tam * sizeof(claves_t));
    
    if (hash->tabla == NULL) {
		free(hash);
		return NULL;
	}
	
	for(i=0;i<tam;i++) {
		(hash->tabla[i].lista_claves)=NULL;     //Inicilizo toda la tabla en NULL
	}
	
	hash->cantidad=0;
	hash->tamanio=tam;
	hash->tabla_redimension=NULL;
	hash->estoy_en_redimension=false;
	hash->destruir_dato=destruir_dato;
	return hash;	
}

size_t hash_cantidad(const hash_t *hash){
	return hash->cantidad;
}

static int obtener_indice(const char *s, const hash_t *hash) {
  int h, a=127;
  for( h=0; *s; s++ )
    h = (a*h + *s) % hash->tamanio;
  return h;
}




void *hash_obtener(const hash_t *hash, const char *clave){
	
	int indice=obtener_indice(clave,hash);
	if((hash->tabla[indice].lista_claves)==NULL) return NULL;
	
	lista_iter_t* iter = lista_iter_crear(hash->tabla[indice].lista_claves);
	
	while(!lista_iter_al_final(iter)) {    //recorro toda la lista, por si hubo colisiones y hay mas de un elemento
		datos_t* datos_aux=lista_iter_ver_actual(iter);
		if((strcmp(clave,datos_aux->clave))==0) {
			lista_iter_destruir(iter);
			return datos_aux->dato;
		}
		lista_iter_avanzar(iter);
	}
	lista_iter_destruir(iter);
	return NULL;
}

void *hash_borrar(hash_t *hash, const char *clave) {
	
	int indice=obtener_indice(clave,hash);
	if((hash->tabla[indice].lista_claves)==NULL) return NULL;
	
	lista_iter_t* iter = lista_iter_crear(hash->tabla[indice].lista_claves);
	while(!lista_iter_al_final(iter)) {    //recorro toda la lista, por si hubo colisiones y hay mas de un elemento
		datos_t* datos_aux=lista_iter_ver_actual(iter);
		if((strcmp(clave,datos_aux->clave))==0) {
			void* char_dato_aux;
			char_dato_aux=datos_aux->dato;
			free(datos_aux->clave);
			free(datos_aux);
			lista_borrar(hash->tabla[indice].lista_claves,iter);
			
			lista_iter_destruir(iter);
			(hash->cantidad)--;
			
			if(lista_esta_vacia(hash->tabla[indice].lista_claves)) {
				free(hash->tabla[indice].lista_claves);
				hash->tabla[indice].lista_claves=NULL;
			}
			
			return char_dato_aux;
		}
		lista_iter_avanzar(iter);
	}
		
	lista_iter_destruir(iter);
	return NULL;	
}

datos_t *crear_clave_dato(const char *clave, void *dato) {
	datos_t* claveDato = malloc(sizeof(datos_t));
	if (!claveDato) return NULL;
	
	int largo=strlen(clave);
	
	char* nuevaClave = malloc((largo+1)*sizeof(char));
	strcpy(nuevaClave,clave);
	
	claveDato->clave=nuevaClave;
	claveDato->dato=dato;
	return claveDato;
}

void redimensionar(hash_t* hash) {
	
	size_t aumento= 1001;
	int i;
	
	hash->estoy_en_redimension=true; //para que no rediemnsione dentro de una redimension, al irse a hash_guardar
	hash->tabla_redimension = hash->tabla;
	
	hash->tamanio = (hash->tamanio) + aumento;
	
	hash->tabla = malloc((hash->tamanio) * sizeof(claves_t));
    
    for(i=0;i<(hash->tamanio);i++) {
		(hash->tabla[i].lista_claves)=NULL;     //Inicilizo toda la tabla en NULL
	}
    
	for(i=0; i<((hash->tamanio) - aumento); i++) { //paso la tabla vieja a la nueva
		if(hash->tabla_redimension[i].lista_claves){
			while(!lista_esta_vacia(hash->tabla_redimension[i].lista_claves)) {
				datos_t* datos_aux = lista_borrar_primero(hash->tabla_redimension[i].lista_claves);
				hash->cantidad--;
			
				hash_guardar(hash,datos_aux->clave,datos_aux->dato);
				free(datos_aux->clave);
				free(datos_aux);
			}
			free(hash->tabla_redimension[i].lista_claves);
			hash->tabla_redimension[i].lista_claves=NULL;
		}
	}
	
	free(hash->tabla_redimension);
	
	
}

bool hash_guardar(hash_t *hash, const char *clave, void *dato) {
	
	int indice=obtener_indice(clave,hash);
	
	if((hash->tabla[indice].lista_claves)==NULL) { //Creo la lista de claves
		hash->tabla[indice].lista_claves=lista_crear();
		datos_t* claveDato = crear_clave_dato(clave,dato);
		lista_insertar_primero(hash->tabla[indice].lista_claves,claveDato);
		(hash->cantidad)++;
		return true;
	}
	
	lista_iter_t* iter = lista_iter_crear(hash->tabla[indice].lista_claves);
	
	while(!lista_iter_al_final(iter)) {    //recorro la lista por si encuentro exactamente la misma clave
		datos_t* datos_aux=lista_iter_ver_actual(iter);
		
		if((strcmp(clave,datos_aux->clave))==0) { 
			datos_t* claveDato = crear_clave_dato(clave,dato);
			lista_insertar(hash->tabla[indice].lista_claves,iter,claveDato);
			lista_iter_destruir(iter);
			return true;
		}
		lista_iter_avanzar(iter);
	}
	
	lista_iter_destruir(iter);
	
	datos_t* claveDato = crear_clave_dato(clave,dato);
	lista_insertar_ultimo(hash->tabla[indice].lista_claves,claveDato);
	(hash->cantidad)++;
	
	if(lista_largo(hash->tabla[indice].lista_claves)>5 && !(hash->estoy_en_redimension)) {
		
		redimensionar(hash);
		hash->estoy_en_redimension=false;
	}
		
	return true;
}


bool hash_pertenece(const hash_t *hash, const char *clave){
	
	int indice=obtener_indice(clave,hash);
	if((hash->tabla[indice].lista_claves)==NULL) return false;	

	lista_iter_t* iter = lista_iter_crear(hash->tabla[indice].lista_claves);
	
	while(!lista_iter_al_final(iter)) {    //recorro toda la lista, por si hubo colisiones y hay mas de un elemento
		datos_t* datos_aux=lista_iter_ver_actual(iter);
		if((strcmp(clave,datos_aux->clave))==0) {
			lista_iter_destruir(iter);
			return true;
		}
		lista_iter_avanzar(iter);
	}
	lista_iter_destruir(iter);
	return false;
}

void hash_destruir(hash_t *hash) {
	
	int indice;
	
	for(indice=0;indice<(hash->tamanio);indice++) {
                
		if((hash->tabla[indice].lista_claves)) {
                
			lista_iter_t* iter = lista_iter_crear(hash->tabla[indice].lista_claves);
                
            while(!lista_iter_al_final(iter)) {    
                
                datos_t* datos_aux=lista_iter_ver_actual(iter);
                free(datos_aux->clave);
                
				if(hash->destruir_dato) {
					 
                    (hash->destruir_dato)(datos_aux->dato);
                }
                lista_iter_avanzar(iter);
            }
            lista_iter_destruir(iter);
            lista_destruir(hash->tabla[indice].lista_claves,free);          
        }
    }

	free(hash->tabla);
	free(hash);
}

bool hash_iter_avanzar(hash_iter_t *iter) {
	
	if(!iter->iter_l) return false;
	
	if(!lista_iter_al_final(iter->iter_l)) {
		lista_iter_avanzar(iter->iter_l);
		if(lista_iter_al_final(iter->iter_l)) {
			size_t indice=iter->pos;
			indice++;
			
			while(indice<iter->tam_hash) {
				if(iter->tabla[indice].lista_claves) {
					free(iter->iter_l);
					lista_iter_t* iter_nuevo=lista_iter_crear(iter->tabla[indice].lista_claves);
					
					iter->iter_l=iter_nuevo;
					iter->pos=indice;
					return true;
				}
				indice++;
			}
			return false;
		}
		return true;
	}
	
	if(lista_iter_al_final(iter->iter_l)) {
		size_t indice=iter->pos;
		indice++;
			
		while(indice<iter->tam_hash) {
			if(iter->tabla[indice].lista_claves) {
				free(iter->iter_l);
				lista_iter_t* iter_nuevo=lista_iter_crear(iter->tabla[indice].lista_claves);
					
				iter->iter_l=iter_nuevo;
				iter->pos=indice;
				return true;
			}
			indice++;
		}
		return false;
	}
	return true;	
}
const char *hash_iter_ver_actual(const hash_iter_t *iter) {
	
	if (!iter->iter_l) return NULL;
	
	datos_t* datos_aux=lista_iter_ver_actual(iter->iter_l);
	
	if (!datos_aux) return NULL;
	
	return datos_aux->clave;
	
}
bool hash_iter_al_final(const hash_iter_t *iter) {
	
	size_t indice=iter->pos;
	
	if(!iter->iter_l) return true; //Si no esta apuntando a ninguna lista, 
								   //es porque esta al final (se creo en un hash vacio)
	if(!lista_iter_al_final(iter->iter_l)) return false;
	
	indice++;
	
	while(indice<iter->tam_hash) {
		if(iter->tabla[indice].lista_claves) return false;
		indice++;
	}
	return true;	
}

void hash_iter_destruir(hash_iter_t* iter) {
	
	if(iter->iter_l) free(iter->iter_l);
	free(iter);	
}

